\documentclass{classrep}
\usepackage[utf8]{inputenc}
\usepackage{color}

\studycycle{Informatyka, studia dzienne, II st.}
\coursesemester{III}

\coursename{Komputerowe systemy rozpoznawania}
\courseyear{2013/2014}

\courseteacher{dr hab. inż. Adam Niewiadomski, prof. nadzw.}
\coursegroup{poniedziałek, 10:30}

\author{
  \studentinfo{Rafał Mościński}{nr 186844} \and
  \studentinfo{Marcin Kubczak}{nr 186834} 
}

\title{Zadanie Numer 1: ekstrakcja cech, miary podobieństwa, klasyfikacja.}

\begin{document}
\maketitle

\section{Cel}
{
Celem zadania jest implementacja algorytmu klasyfikującego  dokumenty tekstowe przy użyciu metody k najbliższych sąsiadów oraz analiza jego skuteczności dla różnych parametrów wejściowych oraz różnych zbiorów danych. Klasyfikacja polega na nadaniu etykiety dokumentowi spośród określonego zbioru etykiet w oparciu o  zbiór dokumentów treningowych.
}

\section{Wprowadzenie}
{

Zrealizowano klasyfikację dokumentów tekstowych algorytmem k najbliższych sąsiadów według dwóch wariantów. Pierwszy wariant algorytmu polega na ekstrakcji cech  dokumentu tekstowego uzyskując w ten sposób wektor liczbowy opisujący ten dokument. Najbliżsi sąsiedzi wyznaczani są poprzez obliczenie odległości pomiędzy wektorami wykorzystując do tego zadaną metrykę odległości.
W drugim wariancie rozwiązanie otrzymywane jest poprzez wyznaczenie podobieństwa dokumentów w oparciu o określone miary podobieństwa pomijając w ten sposób proces ekstracji cech.

Przed przystąpnieniem do klasyfikacji danych tekstowych do poetykietowanych zbiorów wykonane zostało wstępne przetworzenie danych.

\subsection{Wstępne przetworzenie danych} 
{

Preprocesing ma na celu przygotowanie danych do klasyfikacji. W przypadku zadania wykonywanego w ramach laboratorium  polegał on na przetworzeniu dokumentu tekstowego w celu usunięcia z niego znaków które nie niosą ze sobą żadnych istotnych informacji. W tym celu wykonano następujące operacje:

\begin{enumerate}
\item pominięto najczęściej występujące słowa
\item usunięto znaki interpunkcyjne
\item zmieniono wszystkie duże litery na małe.
\end{enumerate}
}

W kolejnych podrozdziałach opisane zostaną ekstraktory użyte do wyodrębnienia cech z dokumentów, miary użyte do oceny podobieńswa dokumentów oraz metryki użyte do obliczenia odległości między wektorami.

\subsection{Ekstrakcja cech}\label{chap:ekstraktory}
{

Dla każdego dokumentu wyekstrahowano zestaw cech dostając w ten sposób wektor liczbowy. Poniżej przedstawiono ekstraktory cech jakie zastosowano:

\begin{itemize}
\itemsep1em
\item ekstraktor znajdujący najczęściej występujące pary słów. Z tekstu wyodrębniana jest określona przez użytkownia ilość najczęściej występujących par słów. Ilość ta określa zarazem długość wektora cech. Każdy element wektora określa ilość znalezionych par słów w tekście. 
%Ekstrakcja składa się z dwóch etapów. W pierwszym etapie, Ekstraktor w klasie GlobalWordsCount zlicza wystąpienia wszystkich słów we wszystkich dokumentach. Ekstraktor PairOfWordsGlobal zlicza najczęściej występujące pary słów dla wszystkich dokumentów, następnie usuwa połowę najrzadziej występujących par. W kolejnym kroku ekstraktor PairOfWordsFeature zlicza wystąpienia par słów znalezionych w poprzednim kroku dla każdego dokumentu.%


\item NumbersWordsExtractor -- Ekstraktor znajdujący najczęściej pojawiajace się słowa  przy wartościach liczbowych występujących w tekście. Ekstraktor ten działa analogicznie jak powyższy jednak zamiast pary słów wyodrębniane są liczby występujące w tekstach oraz słowo najczęściej pojawiające się razem z daną liczbą. Wektor cech tworzony jest analogicznie jak dla ekstraktora opisanego powyżej.

\item NumbersExtractor -- ekstraktor, który dla każdego z dokumentów wybiera N największych liczb, umieszczając je następnie w wektorze cech.

\item GlobalClassesWordCountExtractor -- ekstraktor, który zlicza wystąpienia N najbardziej popularnych słów występujących w danej klasie. Słowa te znajdywane są wśród dokumentóW wchodzących w skład zbioru uczącego z użyciem klasy GlobalClassesWordCount.

%\item \color{red}TUTAJ opis pozostałych cech \color{red}

\end{itemize}

\subsection{Metryki odległości}\label{chap:metryki}

Poniżej przedstawiono metryki odległości jakie zostały wykorzystane do obliczenia odległości między wektorami.


\begin{itemize}
\item Metryka euklidesowa
\begin{equation}
d(V_{1}, V_{2})=\sqrt{\sum_{i=1}^{n}(v_{1i}-v_{2i})^{2}}
\end{equation}
\item Metryka uliczna
\begin{equation}
d(V_{1}, V_{2})=\sum_{i=1}^{n}\left |v_{1i}-v_{2i}  \right |
\end{equation}
\item Metryka Czebyszewa
\begin{equation}
d(V_{1}, V_{2})={max}\left |v_{1i}-v_{2i}  \right | , {i=1,...,n}
\end{equation}
\end{itemize}

\subsection{Trening klasyfikatora kNN}
{

W wariancie korzystającym z ekstraktorów cech wykonano normalizację zbioru danych treningowych według następującego wzoru:

\begin{equation}
x^n_i = \frac{x_i - min(x_i)}{max(x_i) - min(x_i)}, 0 \leq x^2_i \leq 1
\end{equation}

\subsection{Miary podobieństwa}\label{chap:miarypodob}
{
Poniżej przedstawiono użyte miary podobieństwa.

\subsubsection{Uogólniona miara n-gramów z ograniczeniami.}
{
Podobieństwo dokumentów tekstowych s1,s2 określane jest w oparciu o ilość wspólnych podciągów n-elementowych. Uwzględniane są przy tym górne i dolne ograniczenia długości podciągów których występowanie w porównywanych słowach będzie sprawdzane. Końcowa miara podobieństwa obliczana jest jako całkowita suma wspólnych podciągów każdego słowa z każdym innym w dwóch danych dokumentach podzielona przez ilość wszystkich możliwych do otrzymiania podciągów.


\begin{equation}
\mu_{n}(s_{1}, s_{2})=f(N,n_{1},n_{2})\sum_{i=n_{1}}^{n_{2}}\sum_{i=1}^{N(s_{1})-i+1}h(i,j)
\end{equation}
\\
gdzie
\begin{equation}
f(N, n_{1},n_{2}) = \frac{2}{(N - n_{1} + 1)(N - n_{1} + 2) - (N - n_{2} + 1)(N - n_{2})}
\end{equation}
\\
h(i, j) = 1, jeśli i-elementowy podciąg w słowie s1 zaczynający się od j-tej pozycji w słowie s1 pojawia się przynajmniej raz w słowie s2.
\\
h(i, j) = 0), w przeciwnym wypadku
\\\\
N (s1 ), N (s2 ) – ilość liter w słowach s1 i s2
\\
N = max{N (s1 ), N (s2 )
\\
n1 - dolne ograniczenie
\\
n2 - górne ograniczenie

}
\subsubsection{Term Frequency Matrix}
{
Podobieństwo dokumentów d1 i d2 określane jest w oparciu o zbiór terminów t1, t2, .., tn. Terminy te są słowami najczęściej występującymi w dokumencie d1. Następnie w dokumencie d2 szukane są te same słowa które znalezione zostały w dokumencie d1 i tworzone są wektory których wartościami jest ilość wystąpień  poszczególnych terminów w danym dokumencie.

\begin{table}[h!]
\centering

\begin{tabular}{|c|c c c c|}
\hline
 & t1 & t2 & ... & tn\\
\hline
d1 & a11 & a12 & ... & a1n\\
d2 & a21 & a22 & ... & a2n\\
\hline
\end{tabular} 

\end{table}
\newpage
Końcową miarę podobieństwa oblicza się przy pomocy amplitudy kosinusowej danej poniższym wzorem: 

\begin{equation}
r_{ca}(D_{1}, D_{2}) = \frac{\left | \sum_{i=1}^{n} d _{1i}\cdot d_{2i}  \right |}{\sqrt{\sum_{i=1}^{n}d_{1i}^{2} \cdot \sum_{i=1}^{n} d_{2i}^{2}}}
\end{equation}

}
\subsection{Klasyfikacja}
{
Klasyfikacja dokumentu do danego zbioru wykonana została poprzez wyznaczenie dla niego k najbliższych sąsiadów i zakwalifikowanie do tego zbioru do którego należy większość sąsiadów. Dla wariantu pierwszego najbliższymi sąsiadami są dokumenty dla których odległość między ich wektorami cech jest najmniejsza. W wariancie drugim za najbliższych sąsiadów uznaje się dokumenty dla których podobieństwo obliczone według określonej miary jest największe.
}

\section{Opis implementacji}
{
Aplikacja napisana została w języku programowania Java. Użytkownik ma możliwość  wyboru wariantu algorytmu kNN według którego dane będą klasyfikowane (tj. według metryki odległości lub według miary podobieństwa). Ponadto jest możliwość wyboru jakie eksktraktory cech bądź miara podobieństwa mają zostać użyte. Kolejnym parametrem ustawianym przez użytkownika jest zbiór jaki ma zostać użyty, oraz w przypadku zbioru Reuters kategoria jaka ma być testowana. Ponadto użytkownik może określić jaki procent całego zbioru ma zostać przeznaczony na dane treningowe.}

\section{Materiały i metody}
{

W celu określenia skuteczności algorytmu kNN wykonano szereg testów dla różnych parametrów wejściowych. Parametry wyznaczane są w dwóch etapach. W pierwszym etapie wyznaczono  współczynnik K dla algorytmu kNN dla którego skuteczność klasyfikacji była największa. Do tych eksperymentów wykorzystano metrykę Euclidesową oraz wszystkie ekstraktory cech opisane w rozdziale. Dane podzielone zostały w stosunku 60\% treningowych oraz 40\% testowych ~\ref{chap:ekstraktory}.


Wykonane zostały testy dla następujących wartości parametru K:

\begin{table}[h!]
\centering
\caption{Testy - etap 1}

\begin{tabular}{|c|c|}
\hline
K\\
\hline
1, 5, 9, 13, 17, 21, 25, 29, 33, 37\\
\hline
\end{tabular} 

\end{table}

W drugim etapie wyznaczono skuteczność każdego ekstraktora z osobna dla trzech różnych metryk odległości opisanych w rozdziale ~\ref{chap:metryki}. Użyty został przy tym najlepszy współczynnik K oraz 60\% danych treningowych i 40\%  danych testowych całego zbioru.


Wykonane zostały testy dla następujących zestawów parametrów:

\begin{table}[h!]
\centering
\caption{Testy - etap 2}

\begin{tabular}{|c|c|}
\hline
Nazwa ekstraktora & Metryka\\
\hline
Para słów & Euklides\\
\hline
Para słów & Czebyszew\\
\hline
Para słów & Uliczna\\
\hline
Para liczba-słowo & Euklides\\
\hline
Para liczba-słowo & Czebyszew\\
\hline
Para liczba-słowo & Uliczna\\
\hline
Ekstraktor największa liczba & Euklides\\
\hline
Ekstraktor największa liczba & Czybyszew\\
\hline
Ekstraktor największa liczba & Uliczna\\
\hline
Ekstraktor słowo-klasa & Euklides\\
\hline
Ekstraktor słowo-klasa liczba & Czybyszew\\
\hline
Ekstraktor słowo-klasa liczba & Uliczna\\

\hline
\end{tabular} 

\end{table}
 \color{black}
Testy przeprowadzone zostały dla dwóch zbiorów danych. 

Pierwszym z nich jest zbiór Reuters. Ze zbioru wyodrębniono dokumenty które posiadają jedną etykietę w polu "places" oraz "people". Przefiltrowano dokumenty pozostawiając te które mają przypisaną jedną z 6 etykiet w kategorii "places" wymienionych poniżej:

\begin{itemize}
\item "west-germany"
\item "usa"
\item "france"
\item "uk"
\item "canada"
\item "japan"
\end{itemize}


Zadanie klasyfiakcji polegało na przypisaniu każdemu dokumentowi ze zbioru testowego jednej z sześciu powyższych  etykiet.

Eksperyment wykonany został także dla zbioru "20 Newsgroup", na który składało się 2000 wiadomości z grup dyskusyjnych, po 100 wiadomości na grupę.

\color{black}

W celu oceny skuteczności miar podobieństwa opisanych w rozdziale ~\ref{chap:miarypodob} przeprowadzono testy dla każdej miary z osoba dla wyznaczonego we wcześniejszych etapach parametru K oraz proporcji danych treningowych do testowych 60\% do 40\%. Przetestowane zostały różne warianty danych wejściowych poszczególnych miar podobieństwa.

Wykonane zostały testy dla następujących zestawów parametrów:

\begin{table}[h!]
\centering
\caption{Testy - dla miary N-gramów z ograniczeniami}

\begin{tabular}{|c|c|c|c|}
\hline
K dla Knn & Train/Test & Dolny zakres N-gram & Górny zakres N-gram\\
\hline
9 & 60/40 & 2-gram & 2-gram\\
\hline
9 & 60/40 & 2-gram & 3-gram\\
\hline
9 & 60/40 & 2-gram & 4-gram\\
\hline
9 & 60/40 & 2-gram & 5-gram\\
\hline
9 & 60/40 & 3-gram & 3-gram\\
\hline
9 & 60/40 & 3-gram & 4-gram\\
\hline
9 & 60/40 & 3-gram & 5-gram\\
\hline
9 & 60/40 & 4-gram & 4-gram\\
\hline
9 & 60/40 & 4-gram & 5-gram\\
\hline
9 & 60/40 & 5-gram & 5-gram\\
\hline

\end{tabular} 

\end{table}
\newpage
\begin{table}[h!]
\centering
\caption{Testy - dla miary Term Frequency Matrix}

\begin{tabular}{|c|c|c|c|}
\hline
K dla Knn & Train/Test & Ilość słów\\
\hline
9 & 60/40 & 5\\
\hline
9 & 60/40 & 10\\
\hline
9 & 60/40 & 15\\
\hline
9 & 60/40 & 20\\
\hline
9 & 60/40 & 25\\
\hline
9 & 60/40 & 30\\
\hline
9 & 60/40 & 35\\
\hline
9 & 60/40 & 40\\
\hline
9 & 60/40 & 45\\
\hline
9 & 60/40 & 50\\
\hline
\end{tabular} 

\end{table}


}

\section{Wyniki}
{

\begin{table}[h!]
\centering
\caption{Testy - dla miary Term Frequency Matrix}

\begin{tabular}{|c|c|c|c|c|}
\hline
K dla Knn & Train/Test & Ilość słów & Skuteczność\\
\hline
9 & 40/60 & 5 & 5,88\%\\
\hline
9 & 40/60 & 10 & 5,88 \%\\
\hline
9 & 40/60 & 15 & 80,33 \%\\
\hline
9 & 40/60 & 20 &80,33\%\\
\hline
9 & 40/60 & 25 &80,33\%\\
\hline
9 & 40/60 & 30 &80,33\%\\
\hline
9 & 40/60 & 35 &80,33\%\\
\hline
9 & 40/60 & 40 &80,33\%\\
\hline
9 & 40/60 & 45 &80,33\%\\
\hline
9 & 40/60 & 50 &80,33\%\\
\hline
\end{tabular} 

\end{table}


\begin{table}[h!]
\centering
\caption{Testy - dla miary N-gram}

\begin{tabular}{|c|c|c|c|c|}
\hline
K dla Knn & Train/Test & Dolna granica N & Górna granica N & Skuteczność\\
\hline
9 & 40/60 & 2 & 2 & 80,31 \%\\
\hline
9 & 40/60 & 2 & 3 & 80,31 \%\\
\hline
9 & 40/60 & 2 & 4 & 80,33 \%\\
\hline
9 & 40/60 & 2 & 5 & 80,29 \%\\
\hline
9 & 40/60 & 3 & 3 & 80,33 \%\\
\hline
9 & 40/60 & 3 & 4 &  80,33 \%\\
\hline
9 & 40/60 & 3 & 5 &  80,33 \%\\
\hline
\end{tabular} 

\end{table}

\begin{table}[h!]
\centering
\caption{Zadanie pierwsze - cechy}

\begin{tabular}{|c|c|c|}
\hline
ekstraktor & k & wynik \\
\hline
GlobalClassesWordCountExtractor(30) & 9 & 79,38\% \\
\hline
GlobalClassesWordCountExtractor(15) &  9 & 78,82\% \\
\hline
GlobalClassesWordCountExtractor(10) & 9 & 75,79\% \\
\hline
GlobalClassesWordCountExtractor(5) & 9 & 68,08\% \\
\hline
GlobalClassesWordCountExtractor(5) & 30 & 64,34\% \\
\hline
NumbersWordsExtractor() & 9 & 3,98\% \\
\hline
NumbersWordsExtractor() & 3 & 3,98\% \\
\hline
NumbersWordsExtractor() & 37 & 5,69\% \\
\hline
NumberExtractor(1) & 10 & 54,18\% \\
\hline
NumberExtractor(1) & 37 & 71,62\% \\
\hline
NumberExtractor(10) & 37 & 72,53\% \\
\hline
NumberExtractor(15) & 100 & 55,19\% \\
\hline
PairsOfWordsExtractor(43) & 25 & 67,26\% \\ 
\hline
PairsOfWordsExtractor(20) & 25 & 72,21\% \\
\hline
PairsOfWordsExtractor(43),& &\\
NumberExtractor(5), & & \\
NumbersWordsExtractor() & 5 & 74,00\% \\
\hline
PairsOfWordsExtractor(10), & & \\
NumberExtractor(10), & & \\
NumbersWordsExtractor() & & \\
GlobalClassesWordCountExtractor(30) & 37 & 78.78\% \\
\hline
\end{tabular}
\end{table}

\begin{table}[h!]
\centering
\caption{Zadanie drugie - cechy}

\begin{tabular}{|c|c|c|}
\hline
ekstraktor & k & wynik \\
\hline
PairsOfWordsExtractor(10)  & 37 & 15,09\% \\
\hline
PairsOfWordsExtractor(10) & 9 & 8,12\% \\
\hline
NumberExtractor(10) & 37 & 2,75\% \\
\hline
NumbersWordsExtractor() & 37 & 5,80\% \\
\hline
GlobalClassesWordCountExtractor(3) & 37 & 8,41\% \\
\hline
PairsOfWordsExtractor(10), & & \\
NumberExtractor(10), & & \\
 NumbersWordsExtractor(),  & & \\
GlobalClassesWordCountExtractor(3) & 37 & 11,75\% \\

\hline
\end{tabular}
\end{table}

\begin{table}[h!]
\centering
\caption{Zadanie trzecie - zbiór własny}

\begin{tabular}{|c|c|c|}
\hline
ekstraktor & k & wynik \\
\hline
PairsOfWordsExtractor(10), & & \\
GlobalClassesWordCountExtractor(3), & & \\
NumbersWordsExtractor(), & & \\
NumberExtractor(10) & 9 & 7,12\% \\
\hline

\end{tabular}
\end{table}


%\section{Dyskusja}
%{\color{blue}
%Sekcja ta powinna zawierać dokładną interpretację uzyskanych wyników
%eksperymentów wraz ze szczegółowymi wnioskami z nich płynącymi. Najcenniejsze
%są, rzecz jasna, wnioski o charakterze uniwersalnym, które mogą być istotne
%przy innych, podobnych zadaniach. Należy również omówić i wyjaśnić wszystkie
%napotakane problemy (jeśli takie były). Każdy wniosek powinien mieć poparcie
%we wcześniej przeprowadzonych eksperymentach (odwołania do konkretnych
%wyników). Jest to jedna z najważniejszych sekcji tego sprawozdania, gdyż
%prezentuje poziom zrozumienia badanego problemu.}
\newpage
\section{Wnioski}
\begin{itemize}

\item Zwiększenie liczby ekstraktorów nie zawsze powoduje polepszenie wyników (np.: GlobalClassesWordCountExtractor(30) ma 79\%, a wszystkie razem 78\%

\item Dla różnych ekstraktorów różne wartości liczby k dawały najwyższą skuteczność. Nie udało się znaleźć uniwersalnej wartości liczby k dla któRej uzyskiwane byłyby najlepsze wyniki dla każdego ekstraktora.

\item Dla metody N-gram najlepszą skuteczność uzyskano dla wartośći dla dolnej i górnej granicy równej odpowiednio 2 i 4 oraz dla 3 i 3.

\item Od 15 słów kluczowych oraz każdej wyzszej wartości osiągnięto taką samą wysoką skuteczność, równą 80,33\%.

\end{itemize}

\begin{thebibliography}{0}
\bibitem{ksr} Niewiadomski, A., \emph{Materiały, przykłady i ćwiczenia do przedmiotu Komputerowe Systemy Rozpoznawania},
http://ics.p.lodz.pl/~aniewiadomski/ksr/ksr-wyklad-2009.pdf
\end{thebibliography}

\end{document}
